#include <iostream>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <iterator>
using namespace std;

typedef vector<int> IntVec;

int chop(int value, const IntVec& integers, int begin = 0, int end = -1) {
	int length = (end == -1 ? integers.size() : end) - begin;
	if (length > 0) {
		int middle = begin + length / 2;
		if (value == integers[middle]) {
			return middle;
		} else if (value > integers[middle]) {
			return chop(value, integers, middle + 1, end);
		} else if (value < integers[middle]) {
			return chop(value, integers, begin, middle);
		}
	}
	return -1;
}

int main(int argc, char* argv[]) {
	IntVec vec0;
	assert(-1 == chop(3, vec0));

	int array1[] = { 1 };
	IntVec vec1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
	assert(-1 == chop(3, vec1));
	assert(0 == chop(1, vec1));

	int array2[] = { 1, 3, 5 };
	IntVec vec2(array2, array2 + sizeof(array2) / sizeof(array2[0]));
	assert(0 == chop(1, vec2));
	assert(1 == chop(3, vec2));
	assert(2 == chop(5, vec2));
	assert(-1 == chop(0, vec2));
	assert(-1 == chop(2, vec2));
	assert(-1 == chop(4, vec2));
	assert(-1 == chop(6, vec2));

	int array3[] = { 1, 3, 5, 7 };
	IntVec vec3(array3, array3 + sizeof(array3) / sizeof(array3[0]));
	assert(0 == chop(1, vec3));
	assert(1 == chop(3, vec3));
	assert(2 == chop(5, vec3));
	assert(3 == chop(7, vec3));
	assert(-1 == chop(0, vec3));
	assert(-1 == chop(2, vec3));
	assert(-1 == chop(4, vec3));
	assert(-1 == chop(6, vec3));
	assert(-1 == chop(8, vec3));

	int array4[] = { 1, 2, 2, 3, 3, 3, 3, 6, 6, 9 };
	IntVec vec44(array4, array4 + sizeof(array4) / sizeof(array4[0]));
	int result = chop(3, vec44);
	assert(3 <= result && result <= 6);

	if (argc > 1) {
		int n = atoi(argv[1]);
		int m = atoi(argv[2]);
		IntVec vec4(n, 0);
		srand(time(0));
		for (int i = 0; i < n; i++) {
			vec4[i] = rand() % m;
		}
		sort(vec4.begin(), vec4.end());
		int randVal = vec4[rand() % n];
		assert(randVal == vec4[chop(randVal, vec4)]);
	}
}
